/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package data;

import java.util.ArrayList;

import error.InvalidValueException;
import error.ProgrammingErrorException;
import error.Severity;

/**
 * @author jchoy
 *
 */
public class Heap< T extends Comparable<T> > {
    
    private ArrayList<T> dataArray = new ArrayList<T>();
    private static final int MIN_ELEMENT_INDEX = 0;
    
    /**
     * Returns the smallest element in the heap without removing
     * @return The smallest element in the heap. null if empty
     */
    private T getSmallestElement() {
        T min = null;
        
        if ( dataArray.size() > 0 ) {
            min = dataArray.get( MIN_ELEMENT_INDEX );
        }
        
        return min;
    }
    
    /**
     * Returns and removes the smallest element in the heap. Then "sorts" the
     * heap to "Heap Standards"
     * @return The smallest element in the heap. null if empty
     * @throws ProgrammingErrorException If a node has a right child without
     * having a left child.
     */
    public T extractSmallestElement() throws ProgrammingErrorException {
        T smallest = getSmallestElement();
        
        // only "sort" heap if it has data in it
        if ( dataArray.size() > 0 ) {
            
            // Get the last element and move it to the top
            T lastElement = dataArray.remove( getLastElementIndex() );
            
            // If this was the last element, we're done
            if ( dataArray.size() != 0 ) {
                dataArray.set( MIN_ELEMENT_INDEX, lastElement );
                
                // Bubble the element down to the correct place
                bubbleDownElement( MIN_ELEMENT_INDEX );
            }
        }
        
        return smallest;
    }
    
    /**
     * Compares the two children data elements of a node at elementIndex
     * and returns the index of the smaller of the two children. If it only has
     * a left child then it returns the index of the right child. It if has no
     * children, it returns -1.
     * @param elementIndex the index of the node we are evaluating
     * @return the index of the smaller child. -1 if no children.
     * @throws ProgrammingErrorException 
     */
    private int getSmallerChildIndex( int elementIndex )
    throws ProgrammingErrorException {
        int leftChildIndex = getLeftChildIndex( elementIndex );
        int rightChildIndex = getRightChildIndex( elementIndex );
        int retVal = -1;
        
        // if both indeces are negative then we are at a leaf
        if ( (leftChildIndex < 0) && (rightChildIndex < 0) ) {
            return -1;
            
        // If the node only has a right child we have a programming error
        } else if ( leftChildIndex < 0 ) {
            throw new ProgrammingErrorException(
                    "Heap node only has right child");
            
        // If the node only has a left child then return the left child
        } else if ( rightChildIndex < 0 ) {
            return leftChildIndex;
            
        // If we have two children, compare and return the smaller.
        } else {
            T leftChild = dataArray.get(leftChildIndex);
            T rightChild = dataArray.get(rightChildIndex);
            
            if ( leftChild.compareTo( rightChild ) < 0 ) {
                retVal = leftChildIndex;
            } else {
                retVal = rightChildIndex;
            }
        }
        
        return retVal;
    }
    
    /**
     * Bubbles the element down the heap to it's correct place
     * @param elementIndex Index of the element we have to bubble
     * @throws ProgrammingErrorException if a node has a right child without
     * having a left child.
     */
    private void bubbleDownElement( int elementIndex )
    throws ProgrammingErrorException {
        
        /**
         * Store the element in a temporary location and keep track of bubble.
         * Our goal is to bubble the bubble down and then replace the bubble
         * with the element.
         */
        T temp = dataArray.get( elementIndex );
        int bubbleIndex = elementIndex;
        
        while (true) {
            int smallerIndex = getSmallerChildIndex( bubbleIndex );
            
            // If we are at a leaf then we are done
            if ( smallerIndex < 0 ) {
                break;
            }
            
            T smallerElement = dataArray.get( smallerIndex );
            
            /**
             * if the element is greater than the smallerElement, swap the
             * bubble and the smallerElement
             */
            if ( temp.compareTo( smallerElement ) > 0 ) {
                dataArray.set( bubbleIndex, smallerElement );
                bubbleIndex = smallerIndex;
            
            // If the element is smaller, then we are done.
            } else {
                break;
            }
        }
        
        // put the element back at the bubbleIndex
        dataArray.set( bubbleIndex, temp );
    }
    
    /**
     * Adds an element to the Heap
     * @param element Element to add to the heap
     * @throws InvalidValueException if the element is null
     */
    public void addElement( T element ) throws InvalidValueException {
        
        if ( element == null ) {
            String errMsg = "null elements are not allowed!";
            throw new InvalidValueException( Severity.NON_FATAL, errMsg );
        }
        
        // Add the element to the end of the array.
        dataArray.add( element );
        
        // Bubble the element up to the correct place
        bubbleUpElement( getLastElementIndex() );
    }
    
    /**
     * Bubbles the element up the heap to it's correct place
     * @param elementIndex Index of the element we have to bubble
     */
    private void bubbleUpElement( int elementIndex ) {
        T temp = dataArray.get( elementIndex );
        int bubbleIndex = elementIndex;
        
        while (true) {
            int parentIndex = getParentIndex( bubbleIndex );
            
            // If we don't have a parent then we are done
            if ( parentIndex < 0 ) {
                break;
            }
            
            T parentElement = dataArray.get( parentIndex );
            
            /**
             * if the element is smaller than the parentElement, swap the
             * bubble and the parentElement 
             */
            if ( temp.compareTo( parentElement ) < 0 ) {
                dataArray.set( bubbleIndex, parentElement );
                bubbleIndex = parentIndex;
                
            // if the element is bigger, the we are done
            } else {
                break;
            }
        }
        
        // put the element back at the bubbleIndex
        dataArray.set( bubbleIndex, temp );
    }
    
    /**
     * @return the index of the last element in the heap
     */
    private int getLastElementIndex() {
        return dataArray.size() - 1;
    }
    
    /**
     * Calculates the index of the parent node of a particular element
     * @param elementIndex Index of the element in question
     * @return Index of the parent of the element in question. -1 if parent
     * does not exist
     */
    private int getParentIndex( int elementIndex ) {
        if ( elementIndex > 0 ) {
            return ( elementIndex - 1 ) / 2;
        } else {
            return -1;
        }
    }

    /**
     * Calculates the index of the left child of a particular element
     * @param elementIndex Index of the element in question
     * @return Index of the left child of the element in question. -1 if child
     * does not exist
     */
    private int getLeftChildIndex( int elementIndex ) {
        int childIndex = 2 * elementIndex + 1;
        if ( childIndex >= dataArray.size() ) {
            childIndex = -1;
        }
        return childIndex;  
    }
    
    /**
     * Calculates the index of the right child of a particular element
     * @param elementIndex Index of the element in question
     * @return Index of the right child of the element in question. -1 if child
     * does not exist.
     */
    private int getRightChildIndex( int elementIndex ) {
        int childIndex = 2 * elementIndex + 2;
        if ( childIndex >= dataArray.size() ) {
            childIndex = -1;
        }
        return childIndex;  
    }
}
